package Stack;

import java.util.Deque;
import java.util.LinkedList;

/**
 *  题目 ：每日温度
 *  题目详述 ：
 *  给定一个整数数组temperatures，表示每天的温度，
 *  返回一个数组answer，其中answer[i]是指对于第 i 天，下一个更高温度出现在几天后。
 *  如果气温在这之后都不会升高，请在该位置用 0 来代替。
 */
public class EverydayTemperature {
    /**
     * 核心思想 ：（栈中元素必然是递增的，只有未找到更高温度的元素才会加入栈中）
     * 使用栈来存储数组中仍然未找到更高温度的;
     *
     * 结果 ：即，当我们想向结果数组中插入结果时，即需要满足（1）栈中元素不为空（2）所新插入的元素大于栈顶元素；
     * ===》 即，将栈顶元素其所对应结果数组索引，与当前的所新插入元素的数组索引进行运算；
     * @param temperatures
     * @return
     */
    public int[] dailyTemperatures(int[] temperatures) {
        int[] results = new int[temperatures.length]; // 定义结果数组的大小
        Deque<Integer> stack = new LinkedList<>();  // 使用栈来存储数组中仍然未找到更高温度的
        for(int i = 0; i < temperatures.length; i++) {
            // 栈中元素：从栈顶到栈底来说，必然是递增的，否则的话，不满足更高的温度一说
            // 即，我们只需要将栈顶元素与数组中的元素进行比较，直到（1）栈为空/（2）数组中的元素 < 栈顶元素
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                // 尤其仅当栈不为空，同时数组中的元素大于栈顶元素时，才能够对于 结果数组进行赋值
                int prev = stack.pop();
                // 注意 ：此处所需要的结果数组索引为 prev（即，为已经出栈的数组元素填入其更高温度的结果）
                results[prev] = i - prev;
            }
            // （1）若是栈中为空时，直接将数组中的元素插入栈中 （2）若是数组中的元素小于等于栈顶元素，也是直接将数组中的元素插入栈中；
            stack.push(i);
        }
        return results;
    }
}
